package list

import "gitee.com/guuzaa/algorithm/constraints"

type Pair[T constraints.Ordered] struct {
	val T
	idx int
}

// Problem Definition: https://leetcode.cn/problems/count-of-smaller-numbers-after-self/
func countSmaller[T constraints.Ordered](nums []T) []int {
	arr := make([]Pair[T], len(nums))
	for i := range arr {
		arr[i] = Pair[T]{val: nums[i], idx: i}
	}

	count := make([]int, len(nums))
	temp := make([]Pair[T], len(nums))
	var sort func(arr []Pair[T], low, high int)
	merge := func(arr []Pair[T], low, mid, high int) {
		for i := low; i <= high; i++ {
			temp[i] = arr[i]
		}

		i, j := low, mid+1
		for p := low; p <= high; p++ {
			if i == mid+1 {
				arr[p] = temp[j]
				j++
			} else if j == high+1 {
				arr[p] = temp[i]
				count[arr[p].idx] += j - mid - 1
				i++
			} else if temp[i].val > temp[j].val {
				arr[p] = temp[j]
				j++
			} else {
				arr[p] = temp[i]
				count[arr[p].idx] += j - mid - 1
				i++
			}
		}
	}

	sort = func(arr []Pair[T], low, high int) {
		if low == high {
			return
		}

		mid := low + (high-low)/2

		sort(arr, low, mid)
		sort(arr, mid+1, high)
		merge(arr, low, mid, high)
	}

	sort(arr, 0, len(arr)-1)

	return count
}
